The objectives of this technical report is to provide additional results on the generalized conditional gradient methods introduced by Bredies et al. [BLM05]. Indeed , when the objective function is smooth, we provide a novel certificate of optimality and we show that the algorithm has a linear convergence rate. Applications of this algorithm are also discussed.

For particular sparse optimization problems, among them is the popular tasks, its low computation cost of linear subproblem proximal gradient (PG) based approach ([Beck and Teboulle, evaluation on each iteration leads to superior 2009]; [Nesterov, 2013]). This kind of methods can achieve practical performance. However, the inferior iteration the optimal rate of convergence under certain problem settings, complexity incurs excess number of gradient hence it enjoys low iteration complexity. The periteration evaluations, which can counteract the efficiency cost mainly comes from gradient evaluation and a gained by solving low cost linear subproblem. In proximal map (PM) related to the type of the regularizer. On this paper, we therefore propose a novel algorithm the one hand, due to the optimal iteration complexity, the that requires optimal graduate evaluations as proximal number of gradient evaluations is optimal for PG method.

Structured sparsity is an important modeling tool that expands the applicability of convex formulations for data analysis, however it also creates significant challenges for efficient algorithm design. In this paper we investigate the generalized conditional gradient (GCG) algorithm for solving structured sparse optimization problems---demonstrating that, with some enhancements, it can provide a more efficient alternative to current state of the art approaches. After providing a comprehensive overview of the convergence properties of GCG, we develop efficient methods for evaluating polar operators, a subroutine that is required in each GCG iteration. In particular, we show how the polar operator can be efficiently evaluated in two important scenarios: dictionary learning and structured sparse estimation. A further improvement is achieved by interleaving GCG with fixed-rank local subspace optimization. A series of experiments on matrix completion, multi-class classification, multi-view dictionary learning and overlapping group lasso shows that the proposed method can significantly reduce the training cost of current alternatives.